#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "time.h"
//线性表最大长度，可自行修改
#define MAXSIZE 10
typedef struct {
    int r[MAXSIZE + 1];
    int length;
}SqList;

void opSystem(SqList *L);

void swap(SqList *L,int i,int j);
void check(SqList L,char *string);

void BubbleSort(SqList *L);

void SelectSort(SqList *L);

void InsertSort(SqList *L);

void ShellSort(SqList *L);

void HeapSort(SqList *L);
void HeapAdjust(SqList *L,int s,int m);

void MergeSort(SqList *L);
void Merge(int SR[],int TR[],int i,int m,int n);
void MergePass(int SR[],int TR[],int s,int n);

void QuickSort(SqList *L);
void QSort(SqList *L,int low,int high);
int Partition(SqList *L,int low,int high);

void RadixSort(SqList *L);
void RadixCountSort(int *index,SqList *L);

void BogoSort(SqList *L);
void Shuffle(SqList *L);
int inOrder(SqList L);

int main() {
    setbuf(stdout,NULL);
    SqList L;
    opSystem(&L);
    return 0;
}

void opSystem(SqList *L) {
    int op = 0,judge = 0;
//    程序计时函数
    clock_t start,finish;
    double totalTime;
    SqList list2,listTest;
    srand(time(0));
    for (int i = 1; i < MAXSIZE + 1; ++i) {
        list2.r[i] = rand() % 1000 + 1;
        listTest.r[i] = list2.r[i];
    }
    list2.r[0] = 0;//数组的第0位空出来用作哨兵或零时遍历
    list2.length = MAXSIZE;
    listTest.length = MAXSIZE;
    printf("----------------------------------------------------------\n");
    check(list2,"here is a A disorderly array:");
    printf("Please select your way to sort it:\n");
    printf("1 : Bubble sort\n");
    printf("2 : Select sort\n");
    printf("3 : Insert sort\n");
    printf("4 : Shell sort\n");
    printf("5 : Heap sort\n");
    printf("6 : Merge sort\n");
    printf("7 : Quick sort\n");
    printf("8 : Radix sort\n");
    printf("9 : Bogo sort\n");
    printf("0 : Compare all the sorting algorithms(except BogoSort)\n");
    printf("----------------------------------------------------------\n");
    scanf("%d",&op);
    switch (op) {
        case 1:
            start = clock();
            BubbleSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the BubbleSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 2:
            start = clock();
            SelectSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the SelectSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 3:
            start = clock();
            InsertSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the InsertSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 4:
            start = clock();
            ShellSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the ShellSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 5:
            start = clock();
            HeapSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the HeapSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 6:
            start = clock();
            MergeSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the MergeSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 7:
            start = clock();
            QuickSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the QuickSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 8:
            start = clock();
            RadixSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the RadixSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 9:
            printf("Warning:The BogoSort is just for fun\ndo not use this algorithm to solve sorting of arrays with length greater than 10!!!\n");
            printf("Or it may make your device crashed!!!\n");
            printf("Are you sure to continue? 1.YES,ELSE:NO\n");
            scanf("%d",&judge);
            if (judge != 1) break;
            if (MAXSIZE >= 10) {
                printf("I'm sorry,you can't continue.\n");
                break;
            }
            start = clock();
            BogoSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the BogoSort has use %lf s\n",totalTime);
            opSystem(L);
            break;
        case 0:
//            冒泡
            start = clock();
            BubbleSort(&listTest);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the BubbleSort has use %lf s\n",totalTime);

            for (int i = 1; i < MAXSIZE + 1; ++i) {
                listTest.r[i] = list2.r[i];
            }
            
//            选择
            start = clock();
            SelectSort(&listTest);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the SelectSort has use %lf s\n",totalTime);

            for (int i = 1; i < MAXSIZE + 1; ++i) {
                listTest.r[i] = list2.r[i];
            }
            
//            插入
            start = clock();
            InsertSort(&listTest);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the InsertSort has use %lf s\n",totalTime);

            for (int i = 1; i < MAXSIZE + 1; ++i) {
                listTest.r[i] = list2.r[i];
            }
            
//            希尔
            start = clock();
            ShellSort(&listTest);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the ShellSort has use %lf s\n",totalTime);

            for (int i = 1; i < MAXSIZE + 1; ++i) {
                listTest.r[i] = list2.r[i];
            }
            
//            堆
            start = clock();
            HeapSort(&listTest);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the HeapSort has use %lf s\n",totalTime);

            for (int i = 1; i < MAXSIZE + 1; ++i) {
                listTest.r[i] = list2.r[i];
            }
            
//            归并
            start = clock();
            MergeSort(&listTest);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the MergeSort has use %lf s\n",totalTime);

            for (int i = 1; i < MAXSIZE + 1; ++i) {
                listTest.r[i] = list2.r[i];
            }
            
//            快速
            start = clock();
            QuickSort(&listTest);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the QuickSort has use %lf s\n",totalTime);

            for (int i = 1; i < MAXSIZE + 1; ++i) {
                listTest.r[i] = list2.r[i];
            }

//            基数
            start = clock();
            RadixSort(&list2);
            finish = clock();
            totalTime = (double) (finish - start) / CLOCKS_PER_SEC;
            printf("the RadixSort has use %lf s\n",totalTime);
            
            opSystem(L);
            break;
        default:
            break;
    }
}
//基本操作：交换
void swap(SqList *L,int i,int j) {
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}
//遍历操作
void check(SqList L,char *string) {
    printf("%s\n",string);
    for (int i = 1; i < L.length + 1; ++i) {
        printf("%d ",L.r[i]);
    }
    printf("\n");
}
//冒泡排序
void BubbleSort(SqList *L) {
    for (int i = 1; i <= L->length; ++i) {
        for (int j = i + 1; j <= L->length; ++j) {
            if (L->r[i] > L->r[j]) swap(L,i,j);
        }
    }
    check(*L,"the Bubble Sort result:");
}
//选择排序
void SelectSort(SqList *L) {
    int min;
    for (int i = 1; i <= L->length; ++i) {
        min = i;
        for (int j = i + 1; j <= L->length; ++j) {
            if (L->r[min] > L->r[j]) min = j;
        }
        if (i != min) swap(L,i,min);
    }
    check(*L,"the Select Sort result:");
}
//插入排序
void InsertSort(SqList *L) {
    int i,j;
    for (i = 2; i <= L->length; ++i) {//默认第一个是已经排好的，后面的数往其左右插
        if (L->r[i] < L->r[i - 1]) {
            L->r[0] = L->r[i];
            for (j = i - 1; L->r[j] > L->r[0]; --j) {
                L->r[j + 1] = L->r[j];
            }
            L->r[j + 1] = L->r[0];
        }
    }
    check(*L,"the Insert Sort result:");
}
//希尔排序
void ShellSort(SqList *L) {
    int  i,j;
    int increment = L->length;
    do {
        increment = increment / 3 + 1;
        for (i = increment + 1; i <= L->length; i++) {
            if (L->r[i] < L->r[i - increment]) {
                L->r[0] = L->r[i];//此时的r[0]用做暂存区
                for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment)
                    L->r[j + increment] = L->r[j];
                L->r[j + increment] = L->r[0];
            }
        }
    } while (increment > 1);
    check(*L,"the Shell Sort result:");
}
//堆排序
void HeapSort(SqList *L) {
    int i;
    for (i = L->length / 2;i > 0; i--) {
        HeapAdjust(L,i,L->length);
    }
    for (i = L->length;i > 1; i--) {
        swap(L,1,i);
//        每交换一次，堆中最后一个元素即是最大值，将其忽略掉再进行堆调整
        HeapAdjust(L,1,i - 1);
    }
    check(*L,"the Heap Sort result:");
}
//堆调整
void HeapAdjust(SqList *L,int s,int m) {
    int temp,j;
    temp = L->r[s];
    for (j = 2 * s;  j <= m ; j *= 2) {
//        如果左孩比右孩小，则切换到右孩子进行操作
        if (j < m && L->r[j] < L->r[j + 1]) j++;
//        如果暂存区的元素比目前操作对的元素，则不用进行交换了
        if (temp >= L->r[j]) break;

        L->r[s] = L->r[j];
        s = j;
    }
    L->r[s] = temp;
}
//归并排序(非递归实现）
void MergeSort(SqList *L) {
    int* TR = (int *) malloc(L->length * sizeof (int));
    int k = 1;
    while (k < L->length) {
        MergePass(L->r,TR,k,L->length);
        k *= 2;
        MergePass(TR,L->r,k,L->length);
        k *= 2;
    }
    check(*L,"the Merge Sort result:");
}
//      归并两个序列
void Merge(int SR[],int TR[],int i,int m,int n) {
    int j,k,l;
    //对两个序列进行归并
    for (j = m + 1,k = i;i <= m && j <= n;k++) {
        if (SR[i] < SR[j]) TR[k] = SR[i++];
        else TR[k] = SR[j++];
    }
    //将剩余的SR[i..m]复制到TR
    if (i <= m) {
        for (l = 0; l <= m - i; l++)
            TR[k + l] = SR[i + l];
    }
    //将剩余的SR[j..n]复制到TR
    if (j <= n) {
        for (l = 0; l <= n - j; l++)
            TR[k + l] = SR[j + l];
    }
}
void MergePass(int SR[],int TR[],int s,int n) {
    int i = 1;
    int j;
    while (i <= n - 2 * s + 1) {
    //两两归并
        Merge(SR,TR,i,i + s - 1,i + 2 * s - 1);
        i = i + 2 * s;
    }
    //归并最后两个序列
    if (i < n - s + 1)
        Merge(SR,TR,i,i + s - 1,n);
    else
    //如果最后只有一个序列，则直接copy
        for (j = i;j <= n; j++) {
            TR[j] = SR[j];
        }
}
//快速排序
void QuickSort(SqList *L) {
    QSort(L,1,L->length);
    check(*L,"the Quick Sort result:");
}
//快速排序具体实现
void QSort(SqList *L,int low,int high) {
    int pivot;
    if (low < high) {
        pivot = Partition(L,low,high);
        QSort(L,low,pivot - 1);
        QSort(L,pivot + 1,high);
    }
}
//分区操作
int Partition(SqList *L,int low,int high) {
    int pivot;
    L->r[0] = L->r[low];
    pivot = L->r[low];
    while (low < high) {
        while (low < high && L->r[high] >= pivot) --high;
        L->r[low] = L->r[high];
        while (low < high && L->r[low] <= pivot) low++;
        L->r[high] = L->r[low];
    }
    L->r[low] = L->r[0];
    return low;
}

//基数排序
void RadixSort(SqList *L) {
    int i,x=1;
    int tmp=1;
    int radix[L->length + 1];
    while(x) {
        tmp = tmp * 10;
        x = 0;
        for(i = 1;i <= L->length;i++) {
            radix[i] = L->r[i] % tmp;
            radix[i] = radix[i] / (tmp / 10);
            if(L->r[i] / tmp > 0) x = 1;
        }
        RadixCountSort(radix,L);
    }
    check(*L,"the Radix Sort result:");
}
//基数排序具体实现
void RadixCountSort(int *index,SqList *L) {
    int i;
    int sort[L->length];
    int count[10] = {0,0,0,0,0,0,0,0,0,0};

    for(i = 1;i <= L->length;i++)
        count[index[i]] ++;

    for(i = 1;i < 10;i++)
        count[i]=count[i] + count[i - 1];

    for(i = L->length;i > 0;i--) {
        count[index[i]]--;
        sort[count[index[i]]] = L->r[i];
    }

    for(i = 1;i <= L->length;i++)
        L->r[i]=sort[i - 1];
}
//猴子排序
void BogoSort(SqList *L) {
    static int count;
    while(!inOrder(*L)) {
        Shuffle(L);
        printf("%dth attempt failed!\n",count);
        count++;
    }
    check(*L,"the Bogo Sort result:");
}
//随机打乱
void Shuffle(SqList *L) {
    int index,temp,i;
    static int t1,t2;//静态变量未初始化，默认为0
    srand(t1);
    t1 = rand();
    t2 = time(NULL);
    srand(t1 + t2);

    for(i = 1;i <= L->length;i++)
    {
        index = rand() % (L->length - i + 1) + i;
        if(index != i) {
            temp = L->r[i];
            L->r[i] = L->r[index];
            L->r[index] = temp;
        }
    }
}
//检查是否有序
int inOrder(SqList L) {
    int i = 1;
    // 前一个元素 小于 后一个元素  并且  i+1 小于 数组的长度 
    while(L.r[i] < L.r[i + 1] && ++i <= L.length);
    if(i == L.length) return 1;
    else return 0;
}